package demo9;

import demo4.TreeAndGraph;
import lombok.AllArgsConstructor;
import lombok.Getter;
import lombok.NoArgsConstructor;
import lombok.Setter;

import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedList;
import java.util.List;

/**
 * communication network
 *
 */
@Getter
@Setter
@AllArgsConstructor
public class Graph {
    private  Node root;
    ArrayList<ArrayList<Integer>> list =null;
    public Graph(){
        initGraph();
    }
    private void initGraph(){
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);

        node1.setAdjacent(new Node[]{node2});
        node2.setAdjacent(new Node[]{node3,node4});
        node3.setAdjacent(new Node[]{node4});
        node4.setAdjacent(new Node[]{node5});
        node5.setAdjacent(new Node[]{node1});
        this.root=node1;

        list =new ArrayList<ArrayList<Integer>>(){
            {
                add(new ArrayList<Integer>(){{
                    add(root.data);
                }});
            }
        };


    }
    // a->b
    /**
     * a depend b
     */
    @Setter
    @Getter
    @NoArgsConstructor
    public class Edge {

    }
    @Setter
    @Getter
    @NoArgsConstructor
    public class Dependence {

    }
    @Setter
    @Getter
    @NoArgsConstructor
    public class Node {
        private int data;
        private boolean visited;
        private Node[] adjacent;

        public Node(int data) {
            this.data = data;
        }
        public boolean isContains(int nodeData){
            // node if contain the node
            for (Node node : adjacent) {
                if(node.getData()==nodeData){
                    return true;
                }
            }
            return false;
        }

    }
    private void printList(){
        for (ArrayList<Integer> integers : list) {
            System.out.println(integers.toString());
        }
    }
    private void print(Node node){
        System.out.println(node.getData());
    }

    public void dfs(Node node){
        if(node.adjacent==null || node.adjacent.length==0){
            print(node);
            return;
        }
        node.setVisited(true);
        for (Node node1 : node.adjacent) {
            if(!node1.isVisited()){
                dfs(node1);
            }
        }
        print(node);
    }
    /**
     *
     */
    public void bfs( LinkedList<Node> queue){
        queue.addLast(root);

        while (!queue.isEmpty()){
            root = queue.pollFirst();
            if(root.isVisited()){
                continue;
            }
            if( root.adjacent==null || root.adjacent.length==0){
                print(root);
                continue;
            }
            root.setVisited(true);
            for (Node node : root.adjacent) {
                if(!node.isVisited()){
                    queue.addLast(node);
                }
            }
            print(root);
        }

    }
    // from root =1 to root=5
    private boolean isMatch(Node node,int destNode){
        return node.getData()==destNode;
    }
    private void insertNewNodeDataAboveRootData(int data){
        // [1,2] + [ 3 or 4]
        // adjust the  parent ele of the root ele ,and try contains it
        int oldData=root.data;
        ArrayList<ArrayList<Integer>> destIntegers =new ArrayList<>();
        int size = list.size();
        for (int i = 0; i <size; i++) {
            ArrayList<Integer> integers = list.get(i);
            int lastData =integers.get(integers.size()-1);
            if(oldData==lastData){
                destIntegers.add((ArrayList<Integer>)integers.clone());
                integers.add(data);
            }
        }
        //   copy all of old ele
        if(!destIntegers.isEmpty()){
            list.addAll(destIntegers);
        }

    }
    /**
     * get the last node val in every subList
     * [
     *  [1,2,3]
     *  [1,2,4]
     */
    // use the recurison , no

    public void getTraceWithBfsImprove(int destNode , LinkedList<Node> queue){
        queue.addLast(root);
        while (!queue.isEmpty()){
            root = queue.pollFirst();
            if(root.isVisited()){
                continue;
            }
            if(isMatch(root,destNode)){
                System.out.println("i am got it !!! , print current all trace ,");
                printList();
                System.out.println("============= then  compute the shortest trace======================");
                computeShortestTrace();
                return;
            };
            if( root.adjacent==null || root.adjacent.length==0){
                continue;
            }
            root.setVisited(true);
            for (Node node : root.adjacent) {
                insertNewNodeDataAboveRootData(node.data);
                if(!node.isVisited()){
                    queue.addLast(node);
                }
            }

        }

    }
    //   above get the lastest ele is root.data
    private void computeShortestTrace() {
        int size = list.size();
        int oldData = root.data;
        ArrayList<Integer> minSequence = null;
        int min = 0;
        for (int i = 0; i <size; i++) {
            ArrayList<Integer> integers = list.get(i);
            int lastData =integers.get(integers.size()-1);
            if(oldData==lastData){
                min = Math.min(min,integers.size());
                minSequence=integers;
            }
        }
        System.out.println(minSequence);

    }

    // deepth-first-search or breadth-first-search
    // use the dfs  or bfs
    public Node findThatTrace(){
        return null;
    }


}
